package 哈希表系列;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class IsAnagram {
    //错误写法，忽略了set集合不能添加重复元素
//    public boolean isAnagram(String s, String t) {
//        if(s.length()!=t.length()){
//            return false;
//        }
//
//        Set<Character> a = new HashSet<Character>();
//        for (char c : s.toCharArray()){
//            a.add(c);
//        }
//        for (char c : t.toCharArray()){
//            if(a.contains(c)){
//                a.remove(c);
//            }
//            else {
//                return false;
//            }
//        }
//        if(a.isEmpty())
//            return true;
//        else
//            return false;
//    }

    //哈希表正常写法
//    public boolean isAnagram(String s, String t) {
//        if(s.length()!=t.length()){
//            return false;   //如果s的长度不等于t的长度则返回错误
//        }
//
//        int[] record = new int[26]; //记录出现的个数
//
//        for (char c : s.toCharArray()){
//            record[c-'a'] ++;   //s中出现的字母数量都++
//        }
//
//        for (char c : t.toCharArray()){
//            record[c-'a'] --;   //t中出现的字母数量都--
//        }
//
//        for(int i : record){
//            if(i != 0){
//                return false;   //如果record中有数量不等于0则返回错误
//            }
//        }
//
//        return true;
//    }

    //进阶写法

    /**
     * 对于进阶问题，\text{Unicode}Unicode 是为了解决传统字符编码的局限性而产生的方案，它为每个语言中的字符规定了一个唯一的二进制编码。而 \text{Unicode}Unicode 中可能存在一个字符对应多个字节的问题，为了让计算机知道多少字节表示一个字符，面向传输的编码方式的 \text{UTF}-8UTF−8 和 \text{UTF}-16UTF−16 也随之诞生逐渐广泛使用，具体相关的知识读者可以继续查阅相关资料拓展视野，这里不再展开。
     *
     * 回到本题，进阶问题的核心点在于「字符是离散未知的」，因此我们用哈希表维护对应字符的频次即可。同时读者需要注意 \text{Unicode}Unicode 一个字符可能对应多个字节的问题，不同语言对于字符串读取处理的方式是不同的。
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> table = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            table.put(ch, table.getOrDefault(ch, 0) - 1);
            if (table.get(ch) < 0) {
                return false;
            }
        }
        return true;
    }

}
